Date: Wed, 08 Jan 1997 20:52:36 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>Construction of Regular Grammars from Regular Expressions</TITLE>
</HEAD>
<BODY>
<meta name="description" value="Construction of Regular Grammars from Regular Expressions">
<meta name="keywords" value="handout1">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>Construction of Regular Grammars from Regular Expressions</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
For the purposes of this construction we use regular grammars
which have productions of the form <IMG  ALIGN=BOTTOM ALT="" SRC="img1.gif"> and 
<IMG  ALIGN=BOTTOM ALT="" SRC="img2.gif">.
To generate the the empty language no productions are needed.
To generate the singleton language <IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif"> just use the two
productions <IMG  ALIGN=BOTTOM ALT="" SRC="img4.gif"> and <IMG  ALIGN=BOTTOM ALT="" SRC="img5.gif">.
<P>
For the recursive part of the construction,
let <IMG  ALIGN=MIDDLE ALT="" SRC="img6.gif"> and
<IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif"> be regular
grammars which generate the languages defined by the regular
expression <IMG  ALIGN=BOTTOM ALT="" SRC="img8.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif">, respectively.  We will assume
that <IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">.  Given the regular 
expression <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif"> which is built from the regular expressions
<IMG  ALIGN=BOTTOM ALT="" SRC="img12.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif"> we define a new regular grammar 
<IMG  ALIGN=MIDDLE ALT="" SRC="img14.gif"> which
generates the language defined by <IMG  ALIGN=MIDDLE ALT="" SRC="img15.gif">.
There are three cases to consider:
<P>
Case 1.  <IMG  ALIGN=MIDDLE ALT="" SRC="img16.gif">.  Let <IMG  ALIGN=MIDDLE ALT="" SRC="img17.gif"> be a new
non-terminal. 
<UL><LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img18.gif"> is the start symbol of <IMG  ALIGN=MIDDLE ALT="" SRC="img19.gif">.
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img20.gif">.
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img21.gif">.
</UL>
<P>
Case 2.  <IMG  ALIGN=MIDDLE ALT="" SRC="img22.gif">. 
<UL><LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img23.gif">.
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img24.gif">.
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img25.gif"> and
<IMG  ALIGN=MIDDLE ALT="" SRC="img26.gif">.
</UL>
<P>
Case 3.  <IMG  ALIGN=MIDDLE ALT="" SRC="img27.gif">. Let <IMG  ALIGN=MIDDLE ALT="" SRC="img28.gif"> be a new
non-terminal. 
<UL><LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img29.gif"> is the start symbol for <IMG  ALIGN=MIDDLE ALT="" SRC="img30.gif">.
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img31.gif">.
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img32.gif">
and <IMG  ALIGN=MIDDLE ALT="" SRC="img33.gif">.
</UL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Mon Jan 22 13:09:21 PST 1996</I>
</ADDRESS>
</BODY>
